\subsubsection{Übung viii}

Eine Funktion \(f: X \rightarrow Y\) heißt injektiv gdw.
\[
 \forall x_1, x_2 \in X: f(x_1) = f(x_2) \:\Longrightarrow x_1 = x_2
\]
Zwei verschiedene \(x\) können nicht auf das gleiche \(y\) abgebildet werden bzw.
für jedes \(y \in Y\) gibt es höchstens ein \(x\) mit \(f(x) = y\).

Eine Funktion \(f: X \rightarrow Y\) heißt surjektiv gdw.
\[
 \forall y \in Y \: \exists x \in X: y = f(x)
\]
Für jedes \(y\) gibt es mindestens ein \(x\), das darauf abgebildet wird.

\begin{enumerate}[1)]
\item
Wenn \(|Y| < |X| < \infty\), d.h. \(X\) und \(Y\) sind endliche Mengen und \(Y\) hat weniger Elemente als \(X\),
dann gibt es nicht genügend \(y \in Y\), um jedem \(x \in X\) ein anderes \(y = f(x)\) zuzuweisen.

Es gilt
\[
 \exists x_1, x_2 \in X: f(x_1) = f(x_2) \: \wedge x_1 \not= x_2
\]
Das verstößt gegen die obige Definition der Injektivität, daher ist \(f\) nicht injektiv.
eindeutiges

Bildlich dargestellt für \(|Y| = n,\:|X| = n + 2\):
\[
 \left(\begin{smallmatrix}
  x_1\\
  x_2\\
  x_3\\
  \vdots\\
  x_n\\
  x_n+1\\
  x_n+2
 \end{smallmatrix}\right)
 \begin{smallmatrix}
  \Longrightarrow\\
  \Longrightarrow\\
  \Longrightarrow\\
  \vdots\\
  \Longrightarrow\\
  \Longrightarrow\\
  \Longrightarrow\\
 \end{smallmatrix}
  \left(\begin{smallmatrix}
  y_1\\
  y_2\\
  y_3\\
  \vdots\\
  y_n\\
  ???\; \text{KEIN ELEMENT MEHR VORHANDEN}\\
  ???\; \text{KEIN ELEMENT MEHR VORHANDEN}
 \end{smallmatrix}\right)
\]

\item
\(|Y| = |X| < \infty\), d.h. \(X\) und \(Y\) sind endliche Mengen und haben die gleiche Anzahl Elemente.

Wenn \(f\) surjektiv ist, dann gibt es für jedes \(y \in Y\) mindestens ein \(x \in X\) mit \(y = f(x)\).
Da \(|Y| = |X|\) kann es kein \(x_1, x_2 \in X\) geben mit \(x_1 \not= x_2 \: \wedge f(x_1) = f(x_2)\).
Jedem \(y \in Y\) muss ein \(x \in X\) zugewiesen werden, und da es von beidem gleich viele gibt, muss eine 1-zu-1 Beziehung bestehen.

Wenn \(f\) nicht surjektiv ist, dann gibt es mindestens ein \(y \in Y\), dem kein \(x\) zugewiesen ist (\(\not\exists x: y = f(x)\)).
Da es aber gleich viele \(x\) wie \(y\) gibt, muss zwangsläufig \( \exists x_1, x_2 \in X: f(x_1) = f(x_2) \: \wedge x_1 \not= x_2 \) gelten, d.h. \(f\) ist nicht injektiv.

Damit ist \(f\) bei \(|Y| = |X| < \infty\) genau dann injektiv, wenn \(f\) surjektiv ist.

Ein Beispiel dafür, dass diese Aussage nicht für unendliche Mengen gilt, ist die Funktion
\[
 f: \mathbb{Z} \mapsto \mathbb{N}_0, \: x \mapsto |x|
\]
Die Funktion \(f\) ist surjektiv, aber nicht injektiv, da z.B.
\[
 f\left(-5\right) = f\left(5\right) = 5
\]


\end{enumerate}
